package now_coder.two_pointer.ncs;

public class NC42 {

    public long maxWater(int[] height) {
        if (height == null || height.length == 0)
            return 0;

        long[][] dp = new long[height.length][2];
        dp[0][0] = height[0];
        dp[height.length - 1][1] = height[height.length - 1];

        for (int i = 1; i < height.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], height[i]);
        }

        for (int i = height.length - 2; i >= 0; i--) {
            dp[i][1] = Math.max(dp[i + 1][1], height[i]);
        }

        long ans = 0;
        for (int i = 1; i < height.length - 1; i++) {
            ans += Math.min(dp[i][0], dp[i][1]) - height[i];
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new NC42().maxWater(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(new NC42().maxWater(new int[]{4, 5, 1, 3, 2}));
        System.out.println(new NC42().maxWater(new int[]{3, 1}));
    }

}
